#include <iostream>
#include <vector>

using namespace std;

// 78.子集
// 给出一个集合，其中所有的元素各不相同。求出该集合的所有子集。

class Solution {
private:
    vector<vector<int>> res;
    // 当前考察nums[index]，看是否能放入
    void getPowerSet(vector<int> &nums, int index, vector<int> &subset) {
        // 已经找到一个子集了
        if(index == nums.size()) {
            res.push_back(subset);
            return;
        }

        for(int i = index; i <= nums.size(); i++) {
            subset.push_back(nums[i]);
            getPowerSet(nums, index+1, subset);
            subset.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        res.clear();
        // 边界条件
        if(nums.empty()) {
            return res;
        }

        vector<int> subset;
        getPowerSet(nums, 0, subset);

        return res;
    }
};
int main() {
    vector<int> nums = {1,2,3};
    vector<vector<int>> res = Solution().subsets(nums);

    cout<<res.size()<<endl;
    return 0;
}
